import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import org.junit.Test;

public class MyTest {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        List<Integer> ans=new ArrayList<Integer>();
        HashMap<TreeNode,TreeNode> parentMap=new HashMap<TreeNode,TreeNode>();
        findParent(root, parentMap);
        DFS(target, null, 0, k, parentMap, ans);
        return ans;
    }
    private void findParent(TreeNode node,HashMap<TreeNode,TreeNode> parentMap){
        if(node==null){
            return;
        }
        parentMap.put(node.left, node);
        parentMap.put(node.right, node);
        findParent(node.left, parentMap);
        findParent(node.right, parentMap);
    }
    private void DFS(TreeNode node,TreeNode preNode, int depth,int k,HashMap<TreeNode,TreeNode> parentMap,List<Integer> ans){
        if(node==null){
            return;
        }
        if(depth==k){
            ans.add(node.val);
            return;
        }
        if(node.left!=preNode){
            DFS(node.left, node, depth+1, k, parentMap, ans);
        }
        if(node.right!=preNode){
            DFS(node.right, node, depth+1, k, parentMap, ans);
        }
        if(parentMap.get(node)!=preNode){
            DFS(parentMap.get(node), node, depth+1, k, parentMap, ans);
        }
    }
    public TreeNode creatABitTree(Integer[] nums) {

        if (nums.length == 0 || nums[0] == null) return null;
        if (nums.length == 1) return new TreeNode(nums[0]);
    
        Queue<TreeNode> queue = new LinkedList<>();  // 得用队列
        // 根结点的处理
        TreeNode node = new TreeNode(nums[0]);
        queue.offer(node);
    
        TreeNode temp;
        for (int i = 1; i < nums.length; ) {
            temp = queue.poll();
            if (nums[i] != null) {
                assert temp != null;
                temp.left = new TreeNode(nums[i++]);
                queue.offer(temp.left);
            } else
                i++;
            if (i >= nums.length)
                break;
            if (nums[i] != null) {
                assert temp != null;
                temp.right = new TreeNode(nums[i++]);
                queue.offer(temp.right);
            } else
                i++;
        }
    
    
        return node;
    }
    @Test
    public void test(){
        Integer[] nums={3,5,1,6,2,0,8,null,null,7,4};
        TreeNode root=creatABitTree(nums);
        TreeNode target = root.left; 
        int k = 2;
        System.out.println(distanceK(root, target, k));
    }
}
